1. Field of the Invention
The present invention is related to data processing systems having the ability to recover data from audit trail tapes when failures occur in the system.
2. Description of Background Technology
In certain applications for data processing systems, it is crucial to insure that data is not lost or corrupted. Banking, stock market, and airline reservations, for example, are businesses in which it is essential to insure the system is not down and the data is not unavailable for even short periods of time, and that the correct state of the data base is maintained. Since computer systems are subject to malfunctions and human error, data can be corrupted, made inaccessible or lost altogether. Numerous recovery techniques have been devised to minimize the distortion, and in critical applications to even reconstruct a data base after failure of the system.
A comprehensive review of the recovery techniques that were available for data base systems as of 1978 is described in the article entitled "Recovery Techniques for Database Systems" by Joost S. M. Verhofstad, which appeared in the ACM publication Computing Surveys, Vol. 10, No. 2, Jun. 1978, pp 167-195. As described in the Verhofstad article, there are various levels of the different kinds of recovery that are available from recovery to correct state of the data base to mere crash resistance, which merely maintains the correct state as much as possible by the manner in which data are manipulated and maintained during normal processing. In data base applications in the above-mentioned industries and others where the maintenance of the correct state of a data base is critical, recovery must be made to a correct state. As the Verhofstad article notes, the audit trail technique is the only one of the seven different types of recovery techniques that are described which have the capability of maintaining the data base in the correct state. Audit trails are used to record each change of a data base record as it occurs so that when the systems fails, the files may be restored to the states they were in prior to the failure. Or alternately the records may be backed-out through a particular process.
Audit trail records for large data base systems, particularly those designed for high transaction environments, can become quite voluminous since they contain information about the changes made to data base records and the times and dates when the changes occurred, along with codes to identify the user. In the high transaction environment, there must be a coordinated usage of a shared data base among a number of data processors. Record locking may also be incorporated into such a system to allow a current user to obtain access to a record and to modify it to the exclusion of other users, who may subsequently also obtain and modify the record when the first user is done with the record.
The file, for example, may be the number of seats that are available on a commercial airline where it is apparent that once a reservations agent has obtained the record and assigned a certain seat, and thereby modified the record, that subsequent users of the record must be locked out during the time the first user is modifying the record. In the event a system failure should occur immediately subsequent to the modification of the record by the first user, the audit trail would then come into effect to reconstruct the data base record to the correct state which would show that the seat that was allocated by the last user before the crash of the system and was no longer available for such a reservation.
Data base recovery transaction techniques are discussed in the article entitled "Principles of Transaction-Oriented Database Recovery" by Theo Haerder and Andreas Reuter in the ACM publication Computing Surveys, Vol. 15, No. 4, Dec. 1983, pp 287-317. FIG. 4 of this article on page 294 shows a typical data base management system, which has a volatile data base buffer and output buffers to the log files, which are also volatile, so that information in these are lost whenever the data base management system experiences abnormal failure. An on-line version of the data base is maintained in a direct access disk, while an older achieved copy of the data base is maintained in a tape file. A disk temporary log is used to collect information needed to reconstruct the most recent data base, and a separate archive log is maintained on the tape which contains all of the changes that have been committed to the data base following the storage of the archive copy of the data base.
The Haerder and Reuter article on page 300 defines physical logging of log data to be whenever some part of the physical representation of the data is written to the log. The article goes on to state that the early applications of physical state logging on page level required that a whole page that was modified had to be rewritten to the log. The article further noted that physical transition logging on the page level was known wherein the old, or "before-look" image, and the new, or "after-look" image, states of a page did not have to be written to log as long as the difference between the log are recorded. This difference may be obtained by using exclusive OR circuits (XOR's) to compare the before-look and after-look images of the page. When these differences are obtained and applied to the before-look image of the page, the new or after-look image results. Similarly, if the difference image is applied to the after-look image of the page, it may be used to provide the before-look image.
An article entitled "A Survey of Techniques for Synchronization and Recovery in Decentralized Computer Systems" by Walter H. Kohler was published by the ACM publication Computing Surveys, Vol. 13, No. 2, Jun. 1981, pp 149-183. The article describes the synchronization of access to shared objects and the recovery of objects in spite of system failures or user errors. Starting on page 155, section 2.1 of this article describes the use of locking schemes to insure the inaccessibility of a locked object, such as a record, while it is under the control of one user in a multi-user system, and, therefore, may be in a temporarily inconsistent state with the maintained record on the data base disk. When a second user or transaction attempts to lock an object that is already locked in an application, such as an airline reservation, or banking or stock exchange sale transaction, the second transaction will wait until the original user unlocks the object.
The Kohler article goes on to state that transactions must be "well formed" and two-phase in order to guarantee data base consistency. A transaction is well-formed when it obtains a lock on the object before it is accessed, does not lock an object which is already locked, and before it completes, unlocks each object it locked.
A two-phase locking scheme occurs if no object is unlocked before all objects are locked. In order to accommodate this desired synchronization, requested locks on the same object may be processed in a queue list memory. The use of a queue list memory for a record lock processor is described in co-pending application entitled "Record Lock Processor for Multiprocessing Data System," Ser. No. 07/759,805, filed Sep. 16, 1991, which is a continuation of Ser. No. 07/669,788, filed Mar. 15, 1991, now abandoned, which is a continuation of Ser. No. 07/167,748, filed Mar. 14, 1988, now abandoned. The Kohler article on page 167 notes that the reconstruction of the initial states of all objects usually involves the maintenance of an incremental log of all the changes that were made to objects on non-volatile storage.
A further description of related recovery and locking techniques are described in the articles entitled "The Recovery Manager of the System R Database Manager" by Jim Gray, Paul McJones, Mike Blasgen, Bruce Lindsay, Raymond Lorie, Tom Price, Franc Oputzolu and Irving Traiger, published in the ACM publication Computing Surveys, Vol. 13, No. 2, Jun. 1981, pp 223-242, and "Concurrency Control in Distributed Database Systems" by Philip A. Bernstein and Nathan Goodman, which appeared in the ACM publication Computing Surveys, Vol. 13, No. 2, Jun. 1981, pp 185-221.
During the passing of data in multi user, high-speed, high-transaction systems, cache memories associated with each of the multi processing units are required to achieve adequate execution speeds. Typical large scale main mass memories have typical access times of 300 to 600 nanoseconds, while information can be obtained from the cache memory on the order of 50 nanoseconds or less. For this reason virtually all modern large scale computing systems have cache memories. Cache memories are now being extensively used in minicomputers, and are also appearing even in microcomputers. The principle of the cache memory when used to provide records from a data base for data processing is that for short periods of time a program generally will distribute its memory references nonuniformly over its address space.
For example, in an airline reservation system there are certain times before a flight is to take place in which there generally are a substantially larger number of accesses to the record than there are at other times. The cache memory holds the records that are being used most over a period of time so that information located in the cache memory may be accessed in a much shorter time than that located on the main data base disk. A typical cache memory is, therefore, relatively small, fast and volatile. A comprehensive discussion of cache memories is found in the article entitled "Cache Memories" by Alan Jay Smith published in the ACM publication Computing Surveys, Vol. 14, No. 3, Sep. 1983, pp 473-530.
U.S. Pat. No. 4,654,819 entitled "Memory Back-Up System", issued Mar. 31, 1987 in the names of Jack J. Stiffler, et al. discloses the use of two physically separate memory areas of the main memory. A status block in the main memory is also used to keep track of the updating of the two memory areas. At the end of the storage operation, the first memory area is initially updated and the status block records this updating. Subsequently, the updating is written to the second area. The status block will then record the completion of data entry into the second memory area. Thus if a fault occurs before the first memory element has been modified, the data and starting addresses in the first memory area are what they were before the processing began, and the program can be restarted at this point.
Alternately, if the processing element fails after the writing began in the first area, but before it was completed, the status block in the main memory would indicate the writing operation was not completed and the fault recovery routine would need only to write the contents of the program from the second area into the first. In a like manner, the computer system can recover from a fault which occurs during modification of the program's second area by assigning a new second area to the program and re-copying the contents of the first area into the second area. U.S. Pat. No. 4,819,154 entitled "Memory Back Up System with One Cache Memory and Two Physically Separated Main Memories" issued Apr. 4, 1989, is a continuation of a Stiffler, et. al. U.S. Pat. No. 4,654,819.
U.S. Pat. No. 4,819,159 entitled "Distributed Multiprocess Transaction Processing System and Method" by Dale L. Shipley, et al., issued Apr. 4, 1989, is directed to a communications environment of a fault tolerant processing system having a plurality of processing units. Each of the processing units requires a real time processor and a specialized processor in a local non-volatile memory. Transaction based processing is undertaken which requires locking provisions. The non-volatile memory stores the log for the associated processor. When a processing unit fails, a transaction coordinator in the processor enables another of the plurality of processing units to establish communication with its non-volatile memory means.
The log associated with the processing unit is then scanned to determine entries of information that are inconsistent with information that is stored in the file system. Other processing units are then interrogated to identify inconsistencies between the logs that they have and the log of the failed unit in order to allow the processing unit that failed to commit or abort the transactions it has been assigned. This insures that processing by the failed unit will be consistent with information stored in the file system, so that a second processing unit is thereby enabled to coordinate the transactions that were formerly coordinated with the failed processing unit.
Unisys Corporation has previously developed a data base recovery system for the Universal Data System (UDS). This system was developed for multi processing operation to allow the implementation of both a first recovery scheme called "Quick Look Recovery" and a second recovery scheme termed "Deferred Update Recovery." In Quick Look Recovery, the data base record was stored in the processing cache of the processor which had obtained a lock upon it. In the case of a write lock, before the alteration actually occurred, the before-look image look of the record was written into a storage retention file. The after-look image of the record was then formed in the processing cache until it was needed by a transaction.
Once the transaction was completed the updated record was processed to the audit trail, and then the data base was updated in a two-phase commit process. Completion of the transaction was also noted on the audit trail tape. Thus at the end of the transaction commit, the after-look image would be written on the data base, the before-look image would be present in the retention file, and the updated after-look image information would be present in the audit trail. When recovery was necessary following an error, roll-back was undertaken by reading before-look images from a retention file and writing them back to the data base. This form of recovery is efficient for programs which do a large number of updates before committing.
The other method of operation of the UDS data base recovery system was termed Deferred Update Recovery. The same elements involving the data base, the processing cache, the processor requesting the lock, the audit trail tape and the retention file are employed in this version. With this technique, the data base record is retained in the cache until it has been modified but no before-look image is generated. The fact that the transaction is recoverable and active is recorded by the audit trail. When the transaction commit is requested following a number of updates in the cache, they are first staged to the audit trail, and then they are written to the retention file.
If a system failure occurs before the copies of the updates are written to the retention file and the audit trail, the recovery action is to roll the transaction back. This is acceptable because the data base has not been updated and the requesting transaction has not been notified of completion. The fact that a copy of the update has made it to the audit trail and the retention file is recorded on the audit trail as "commit in progress." If a failure happens after "commit in progress" but before a commit is complete, the recovery action is to roll the transaction forward by copying the updates from the retention file to the data base.
In the normal case of a successful completion, the updates are written to the data base after they are successfully written on the audit trail and the retention file, both of which use non-volatile media.